/*
Use Divide and Conquer.
The pseudo code can be found in page 171
*/

#include <iostream>
using namespace std;

int A[10]={10,8,20,7,14,1,0,35,40,100};

void swap(int *array, int a, int b)
{
	int x = array[a];
	array[a] = array[b];
	array[b] = x;
}

int partition(int *array, int p, int r)
{
	int x = array[r];	// pivot
	int i = p-1;    // i is the index of last element < pivot
	int j;
        for(j=p;j<r;j++)
	{
		if(array[j]<=x)  // find element < pivot
		{
			i++;
			swap(array,i,j);
		}
	} 
	swap(array,i+1,r);
	return (i+1);
}

void quick_sort(int *array, int p, int r)
{
	if(p < r)
	{
		int q = partition(array,p,r);
		quick_sort(array,p,q-1);
		quick_sort(array,q+1,r); 
	}
}

int main()
{
	quick_sort(A,0,9);
	int i=0;
	for(i=0;i<10;i++)
	  cout << A[i] << " ";	
	cout << endl;
        return 0;
}
